package basics.datastructure.list;

import java.util.ArrayList;
import java.util.List;

/**
 * 双链表反转
 * 
 * @author lisy
 */
public class ReverseDoubleList {

	/**
	 * 双链表
	 */
	public static class DoubleNode {
		public int value;
		public DoubleNode last;
		public DoubleNode next;

		public DoubleNode(int data) {
			value = data;
		}
	}
	
	/**
	 * 自动生成双链表
	 */
	public static DoubleNode generateRandomDoubleList(int len, int value) {
		int size = (int) (Math.random() * (len + 1));
		if (size == 0) {
			return null;
		}
		size--;
		DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
		DoubleNode pre = head;
		while (size != 0) {
			DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
			pre.next = cur;
			cur.last = pre;
			pre = cur;
			size--;
		}
		return head;
	}
	
	public static List<Integer> getDoubleListOriginOrder(DoubleNode head) {
		List<Integer> ans = new ArrayList<Integer>();
		while (head != null) {
			ans.add(head.value);
			head = head.next;
		}
		return ans;
	}
	
	/**
	 * 双链表反转比较器
	 */
	public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {
		DoubleNode end = null;
		for (int i = origin.size() - 1; i >= 0; i--) {
			if (!origin.get(i).equals(head.value)) {
				return false;
			}
			end = head;
			head = head.next;
		}
		for (int i = 0; i < origin.size(); i++) {
			if (!origin.get(i).equals(end.value)) {
				return false;
			}
			end = end.last;
		}
		return true;
	}
	
	/**
	 * 双链表反转
	 */
	public static DoubleNode reverseDoubleList(DoubleNode head) {
		DoubleNode pre = null;
		DoubleNode next = null;
		while (head != null) {
			next = head.next;
			head.next = pre;
			head.last = next;
			pre = head;
			head = next;
		}
		return pre;
	}
	
	public static void main(String[] args) {
		int len = 50;
		int value = 100;
		int testTime = 100000;
		System.out.println("test begin!");
		for (int i = 0; i < testTime; i++) {
			
			// 双链表反转
			DoubleNode node = generateRandomDoubleList(len, value);
			List<Integer> list = getDoubleListOriginOrder(node);
			node = reverseDoubleList(node);
			if (!checkDoubleListReverse(list, node)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("test finish!");
	}
}
